package com.atcumt.Carl.Array;

import java.util.*;

public class Array02 {

    /**
     * 寻找两个正序数组的中位数
     * 使用二分法，对K二分，我们需要分别在nums1和nums2中查找第K/2个元素
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums2, 0, nums2, 0, right)) / 2.0;
    }

    private int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
        // 空数组
        if (i >= nums1.length) {
            return nums2[j + k - 1];
        }
        if (j >= nums2.length) {
            return nums1[i + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[i], nums2[i]);
        }

        // 二分
        int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        if (midVal1 < midVal2) {
            return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
        }
    }

    /**
     * 最长连续序列
     * 假设 a 为一个连续序列的左边界，则 a - 1 不可能存在于数组中。
     * 若 a 是一个左边界，继续找 a + 1... 是否存在集合中，记录长度。
     * 输入：nums = [100,4,200,1,3,2]
     * 输出：4
     */
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        Set<Integer> set = new HashSet<>();
        int maxLen = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        for (int a : set) {
            if (set.contains(a - 1)) {
                continue;
            } else {
                int len = 0;
                while (set.contains(a++)) {
                    len++;
                }
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }

    /**
     * 和为 k 的子数组
     * 输入：nums = [1,2,3], k = 3
     * 输出：2
     * 有几种 i、j 的组合，使得从第 i 到 j 项的子数组和等于 k
     * 前缀和：prefixSum[j] - prefixSum[i - 1] ==k
     */
    public int subarraySum(int[] nums, int k) {

        /*
        每个元素对应一个 "前缀和"，遍历数组，根据当前 "前缀和"，在 map 中寻找「与之相减 == k」的历史前缀和;
        当前前缀和与历史前缀和，差分出一个子数组，该历史前缀和出现过 c 次，就表示当前项找到 c 个子数组求和等于 k
        */
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // 初始化容器
        int preSum = 0, count = 0;
        for (int num : nums) {
            preSum += num;
            if (map.containsKey(preSum - k)) {
                count += map.get(preSum - k);
            }
            // 维护前缀和对应个数的 map 容器
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }

    /**
     * 找到数组中消失的数字
     * 输入：nums = [4,3,2,7,8,2,3,1]
     * 输出：[5,6]
     * 桶排序，将 nums[i] 放到理应出现的位置上
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if (nums[i] == i + 1) {
                i++;
                continue;
            }
            int idx = nums[i] - 1; // 理应出现的位置索引
            if (nums[i] == nums[idx]) {
                i++;
                continue;
            }
            // swap(nums[i], nums[idx])
            int temp = nums[i];
            nums[i] = nums[idx];
            nums[idx] = temp;
        }
        List<Integer> list = new ArrayList<>();
        for (int j = 0; j < nums.length; j++) {
            // 消失的数为 j + 1
            if (nums[j] != j + 1) {
                list.add(j + 1);
            }
        }
        return list;
    }

    /**
     * 最短无序连续子数组
     */
    /*方法一*/
    public int findUnsortedSubarray01(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int[] tempNums = nums.clone();
        Arrays.sort(tempNums);
        int left = Integer.MAX_VALUE, right = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != tempNums[i]) {
                left = i;
                break;
            }
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] != tempNums[i]) {
                right = i;
                break;
            }
        }
        return right - left >= 0 ? right - left + 1 : 0;
    }

    /*贪心：找最左(理论最小)和最右(理论最大)关系相反的地方*/
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int small = nums[n - 1], big = nums[0];
        int left = Integer.MAX_VALUE, right = 0; // [1, 2, 3, 4]
        for (int i = 0; i < n; i++) {
            big = Math.max(big, nums[i]);
            if (nums[i] < big) {
                right = i;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            small = Math.min(small, nums[i]);
            if (nums[i] > small) {
                left = i;
            }
        }
        return right - left >= 0 ? right - left + 1 : 0;
    }
}
